#include <stdio.h>
#include <stdlib.h>

// 合并两个已排序的子数组
// void merge(int arr[], int l, int m, int r) {
//     int i, j, k;
//     int n1 = m - l + 1;
//     int n2 = r - m;

//     // 创建临时数组
//     int L[n1], R[n2];

//     // 复制数据到临时数组 L[] 和 R[]
//     for (i = 0; i < n1; i++)
//         L[i] = arr[l + i];
//     for (j = 0; j < n2; j++)
//         R[j] = arr[m + 1 + j];

//     // 合并临时数组回到 arr[l..r]
//     i = 0; // 初始化左子数组的索引
//     j = 0; // 初始化右子数组的索引
//     k = l; // 初始化合并子数组的索引
//     while (i < n1 && j < n2) {
//         if (L[i] <= R[j]) {
//             arr[k] = L[i];
//             i++;
//         } else {
//             arr[k] = R[j];
//             j++;
//         }
//         k++;
//     }

//     // 复制 L[] 中剩余的元素
//     while (i < n1) {
//         arr[k] = L[i];
//         i++;
//         k++;
//     }

//     // 复制 R[] 中剩余的元素
//     while (j < n2) {
//         arr[k] = R[j];
//         j++;
//         k++;
//     }
// }

// 递归实现归并排序
void merge(int arr[], int l, int m, int r)
{
   int n1 = m - l + 1;//把中间点划分给左边
   int n2 = r - m ;
   int i,j,k;
   int temp1[n1];
   int temp2[n2];
   for( i = 0; i < n1; i++)
    {
        temp1[i] = arr[l + i];
    }
    for(j = 0;j < n2; j++)
    {
        temp2[j] = arr[m + 1 + j];
    }
    i = j = 0;//指针复位
    k = l;
    while(i < n1 && j < n2)
    {
        if(temp1[i] < temp2[j])
        {
            arr[k] = temp1[i];
            i++;//i向后指了一位
        }
        //if与if的错误逻辑，如果第一个符合条件，那么第二次会用下一位进行比较，如果再次符合条件则会覆盖第一次的结果
        else if(temp1[i] > temp2[j])
        {
            arr[k] = temp2[j];
            j++;
        }
        k++;
    }
    while(i < n1)
    {
        arr[k] = temp1[i];
        i++;
        k++;
    }
    while(j < n2)
    {
        arr[k] = temp2[j];
        j++;
        k++;
    }
}
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // // 找到中间点
        // int m = l + (r - l) / 2;

        // // 递归排序左右子数组
        // mergeSort(arr, l, m);
        // mergeSort(arr, m + 1, r);

        // // 合并已排序的子数组
        // merge(arr, l, m, r);
        int m = l + (r-l)/2;
        mergeSort(arr,l,m);
        mergeSort(arr,m+1,r);

        merge(arr,l,m,r);
    }
}

// 辅助函数：打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}
